#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

typedef std::vector<std::vector<int> > Tiles;

Tiles result;
std::vector<int> tileCount(3), startPos(3), swaps, bestSwaps;
std::vector<std::vector<int> > cycles(3);
int rowLength, orderID = 0;
int mtxSize;
int globalBest;
int improveCount;

void kiir(const std::string& filename)
{
  std::ofstream ki(filename.c_str());
  ki<<bestSwaps.size()/2<<std::endl;
  for(int i=0;i<bestSwaps.size();++i)
  {
  	ki<<bestSwaps[i] / rowLength << " " << bestSwaps[i] % rowLength << " ";
  	++i;
  	ki<<bestSwaps[i] / rowLength << " " << bestSwaps[i] % rowLength << std::endl;
  }
  ki.close();
}

void showTiles(const Tiles& tiles, std::ostream& o = std::cout)
{
  o<<tiles.size()<<" "<<tiles[0].size()<<std::endl;
  for(int i=0;i<tiles.size();++i)
  {
    for(int j=0;j<tiles[i].size();++j)
    	o<<tiles[i][j]<<" ";
    o<<std::endl;
  }
}

int countType(const Tiles& tiles, int type)
{
  int cc=0;
  for(int i=0;i<tiles.size();++i)
    for(int j=0;j<tiles[i].size();++j)
    	if(tiles[i][j]==type) ++cc;
  return cc;
}

bool ertelmes(int i,int j)
{
    return (0<=i && i<mtxSize/rowLength && 0<=j && j<rowLength);
}

int getTile(const Tiles& tiles, int i)
{
  if (0 > i || i >= mtxSize)
    return -1;
  else
    return tiles[i / rowLength][i % rowLength];
}



int getTile(const Tiles& tiles, int i, int j)
{
  if (!ertelmes(i, j))
    return -1;
  else
    return tiles[i][j];
}

void swap(Tiles& tiles, int a, int b)
{
  cout<<"swap "<<a<<" "<<b<<endl;
  int tmp = getTile(tiles,a);
  tiles[a / rowLength][a % rowLength] = getTile(tiles,b);
  tiles[b / rowLength][b % rowLength] = tmp;
  swaps.push_back(b);
  swaps.push_back(a);
}

int findTile(Tiles& tiles, int targetType, int type)
{
  for(int i=startPos[type];i<startPos[type]+tileCount[type];++i)
    if(getTile(tiles,i) == targetType)
      return i;
  return -1;
}

int fixType(Tiles& tiles, int type)
{
  int cc=0, w=0;
  for(int i=startPos[type];i<startPos[type]+tileCount[type];++i)
  {
  	int foundType = getTile(tiles, i);
  	if(foundType != type)
  	  {
  	  	//cout<<"wrong type "<<foundType<<" at "<<i<<endl;
  	    int newPos = findTile(tiles,type,foundType);
  	    if(newPos > -1)
  	    {
  	      //cout<<"swap "<<i<<" "<<newPos<<endl;
  	      swap(tiles,i,newPos);
  	      ++cc;
  	    }
  	    else
  	    {
  	      //cout<<"o-o. at"<< i << endl;
  	      cycles[type].push_back(i);
  	    }
  	  }
  }
  return cc;
}

void fixCycle(Tiles& tiles, bool direction, int a, int b, int c)
{
  cout<<"cycle csere\n";
	if(direction == false)
	{
	  swap(tiles,a,b);
	  swap(tiles,a,c);
	}
	else
	{
      swap(tiles,a,c);
	  swap(tiles,a,b);
	}
}

void fixCycles(Tiles& tiles)
{
  bool direction = getTile(tiles,cycles[0][0])==1;
  for(int i=0;i<cycles[0].size();++i)
    fixCycle(tiles, direction, cycles[0][i],cycles[1][i],cycles[2][i]);
}

void reset()
{
  swaps.clear();
  startPos.clear();
  startPos.resize(3);
  cycles.clear();
  cycles.resize(3);
}

Tiles parkettazzCore(Tiles tiles,int a,int b,int c)
{
  reset();
  startPos[a] = 0;
  startPos[b] = tileCount[a];
  startPos[c] = tileCount[a]+tileCount[b];
  for(int type=0;type<3;++type)
    fixType(tiles,type);
  if(cycles[0].size() > 0)
    fixCycles(tiles);
  return tiles;
}

void parkettazz(Tiles& tiles, int a,int b,int c)
{
  Tiles t = parkettazzCore(tiles,a,b,c);
  std::cout<<"#swaps of ID_"<<orderID<<": "<<swaps.size()/2<<std::endl;
  if(orderID==0 || (orderID>0 && swaps.size() < bestSwaps.size()))
  {
  	result.clear();
  	bestSwaps.clear();
  	result = t;
  	bestSwaps = swaps;
  }
  ++orderID;
}


void parkettazzWrapper(Tiles& tiles)
{
  rowLength = tiles[0].size();
  parkettazz(tiles,0,1,2);
  parkettazz(tiles,0,2,1);
  parkettazz(tiles,1,2,0);
  parkettazz(tiles,1,0,2);
  parkettazz(tiles,2,1,0);
  parkettazz(tiles,2,0,1);
}

void beolvas(const std::string& filename, Tiles& tiles)
{
  std::ifstream be(filename.c_str());
  int n,m,tmp;
  be>>n>>m;
  tiles.resize(n);
  for(int i=0;i<n;++i)
  {
    tiles[i].resize(m);
    for(int j=0;j<m;++j)
    {
      be>>tmp;
      tiles[i][j]=tmp;
    }
  }
  be.close();
  for(int i=0;i<3;++i)
  	tileCount[i] = countType(tiles,i);
  mtxSize = n*m;
  rowLength = m;
}

Tiles transpose(Tiles& tiles)
{
  Tiles t(tiles[0].size());
  for(int i=0;i<t.size();++i)
    t[i].resize(tiles.size());
  for(int i=0;i<t.size();++i)
  	for(int j=0;j<t[i].size();++j)
  	  t[i][j] = tiles[j][i];
  return t;
}

void solve(Tiles& tiles)
{
  parkettazzWrapper(tiles);
  Tiles transposeTiles = transpose(tiles);
  parkettazzWrapper(transposeTiles);
}

int findTileAfter(int targetType, int sourceType, int pos, Tiles& t, Tiles& ref)
{
  for(int i=pos+1;i<mtxSize;++i)
  {
    if(getTile(t,i)==targetType && getTile(ref,i)==sourceType)
      return i;
  }
  return -1;
}

void reOrder(Tiles t, Tiles& ref)
{
  reset();
  swaps.clear();
  rowLength = ref[0].size();
  mtxSize = (ref.size())*(ref[0].size());
  for(int i=0;i<mtxSize;++i)
  {
    int refType = getTile(ref,i);
    if(getTile(t,i) != refType)
    {
      cout<<"before\n";
      showTiles(t);
      cout<<"wrong at "<<i<<", type "<< getTile(t,i)<<", it should be "<<refType<<endl;
      int newPos = findTileAfter(refType, getTile(t,i), i, t, ref);
      if(newPos>-1)
      {
        
        swap(t,i,newPos);
        //cout<<"after\n";
        //showTiles(t);
      }
      else {
         cycles[getTile(t,i)].push_back(i);
      }
    }
  }
  cout<<cycles[0].size()<<cycles[1].size()<<cycles[2].size()<<endl;
  if(cycles[0].size() > 0)
    fixCycles(t);
  cout<<"end\n";
  showTiles(t);
  std::cout<<"#swaps of ID_"<<orderID<<": "<<swaps.size()/2<<std::endl;
  if(orderID==0 || (orderID>0 && swaps.size() < bestSwaps.size()))
  {
    result.clear();
    bestSwaps.clear();
    result = t;
    bestSwaps = swaps;
  }
  ++orderID;
}

void reOrderWrapper(Tiles& t, Tiles& ref)
{
  reOrder(t,ref);
}

int count(const Tiles& t,const Tiles& ref,int a,int b) {
    int db=0;
    for(int i=0;i<(ref.size())*(ref[0].size());++i)
    {
        if(getTile(t,i)==a && getTile(ref,i)==b)
            ++db;
    }
    return db;
}


int count(const Tiles& t,const Tiles& ref)
{
    return count(t,ref,0,1)+count(t,ref,0,2)+count(t,ref,1,2);
}



bool connected(const Tiles& t,int type) {
    vector<vector<bool> > elerheto;
    elerheto.resize(mtxSize/rowLength);
    for(int i=0;i<mtxSize/rowLength;++i)
        elerheto[i].resize(rowLength,false);
    bool vege = false;
    for(int i=0;!vege;++i)
        if(getTile(t,i)==type) {
            elerheto[i/rowLength][i % rowLength]=true;
            vege = true;
        }

    bool valt=true;
    while(valt) {
        valt = false;
        for(int i=0;i<mtxSize/rowLength;++i)
        for(int j=0;j<rowLength;++j)
            if(!elerheto[i][j] && getTile(t,i,j)==type)
            {
                if(ertelmes(i,j-1) && elerheto[i][j-1]) {
                    elerheto[i][j]=true;
                    valt=true;
                }
                if(ertelmes(i,j+1) && elerheto[i][j+1]) {
                    elerheto[i][j]=true;
                    valt=true;
                }
                if(ertelmes(i-1,j) && elerheto[i-1][j]) {
                    elerheto[i][j]=true;
                    valt=true;
                }
                if(ertelmes(i+1,j) && elerheto[i+1][j]) {
                    elerheto[i][j]=true;
                    valt=true;
                }
            }
    }
    for(int i=0;i<mtxSize/rowLength;++i)
        for(int j=0;j<rowLength;++j)
            if(getTile(t,i,j)==type && !elerheto[i][j])
                return false;
    return true;
}

bool connected(const Tiles& t)
{
    return connected(t,0) && connected(t,1) && connected(t,2);
}

bool safeSwap (const Tiles& ref, int i, int j ,Tiles& temp)
{
    Tiles acttemp = ref;
    swap(acttemp,i,j);
    if (connected(acttemp)) {
        temp = acttemp;
        return true;
    }
    else
        return false;

}

bool improve(const Tiles& t, const Tiles& ref, Tiles& bestRef)
{
  int best = count(t,ref);
  bestRef = ref;
  improveCount++;
//  cerr<<"("<<improveCount<<")";
  if(improveCount>1000)
    return false;
  for(int a=0;a<3;++a)
      for(int b=a+1;b<3;++b)
      {
          vector<int> hatar,hatarRev;
          for(int i=0;i<mtxSize/rowLength;++i)
          for(int j=0;j<rowLength;++j)
          {
            if(getTile(ref,i,j)==a && getTile(t,i,j)==b && getTile(ref,i-1,j)==b)
                hatar.push_back(i*rowLength+j);
            if(getTile(ref,i,j)==a && getTile(t,i,j)==b && getTile(ref,i+1,j)==b)
                hatar.push_back(i*rowLength+j);
            if(getTile(ref,i,j)==a && getTile(t,i,j)==b && getTile(ref,i,j-1)==b)
                hatar.push_back(i*rowLength+j);
            if(getTile(ref,i,j)==a && getTile(t,i,j)==b && getTile(ref,i,j+1)==b)
                hatar.push_back(i*rowLength+j);

            if(getTile(ref,i,j)==b && getTile(t,i,j)==a && getTile(ref,i-1,j)==a)
                hatarRev.push_back(i*rowLength+j);
            if(getTile(ref,i,j)==b && getTile(t,i,j)==a && getTile(ref,i+1,j)==a)
                hatarRev.push_back(i*rowLength+j);
            if(getTile(ref,i,j)==b && getTile(t,i,j)==a && getTile(ref,i,j-1)==a)
                hatarRev.push_back(i*rowLength+j);
            if(getTile(ref,i,j)==b && getTile(t,i,j)==a && getTile(ref,i,j+1)==a)
                hatarRev.push_back(i*rowLength+j);
           }

          for(int i=0;i<hatar.size();++i)
            for(int j=0;j<hatarRev.size();++j)
                {
                    Tiles temp;
                    if (safeSwap(ref,hatar[i],hatarRev[j],temp)) {
                        Tiles act;
                        improve(t,temp, act);
                        if(count(t,act) < best) {
                            best = count(t,act);
                            bestRef = act;
                        }
                    }
                }
        }
    if(globalBest > best)
    {
        cerr<<best<<endl;
        showTiles(bestRef);
        globalBest = best;
    }
    return (best < count(t,ref));
}

Tiles buildRowStyleTiles(const Tiles& t,int a,int b,int c)
{
    Tiles res;
    res.resize(mtxSize/rowLength);
    for(int i=0;i<mtxSize/rowLength;++i)
        res[i].resize(rowLength);
    for(int i=0;i<mtxSize;++i)
    {
        if(i<countType(t,a))
            res[i/rowLength][i%rowLength]=a;
        else if(i<countType(t,a)+countType(t,b))
            res[i/rowLength][i%rowLength]=b;
        else
            res[i/rowLength][i%rowLength]=c;
    }
    return res;
}

Tiles buildColumnStyleTiles(const Tiles& t,int a,int b,int c)
{
    Tiles res;
    res.resize(mtxSize/rowLength);
    for(int i=0;i<mtxSize/rowLength;++i)
        res[i].resize(rowLength);
    for(int i=0;i<mtxSize;++i)
    {
        if(i<countType(t,a))
            res[i%(mtxSize/rowLength)][i/(mtxSize/rowLength)]=a;
        else if(i<countType(t,a)+countType(t,b))
            res[i%(mtxSize/rowLength)][i/(mtxSize/rowLength)]=b;
        else
            res[i%(mtxSize/rowLength)][i/(mtxSize/rowLength)]=c;
    }
    return res;
}

int main(int argc, char** argv)
{
  if(argc == 2)
  {
    Tiles tiles;
    beolvas(argv[1], tiles);
    solve(tiles);
    std::cout<<"Best: "<<bestSwaps.size()/2<<std::endl;
    //std::cout<<"Result\n";
    std::ofstream ki("solution.txt");
    showTiles(result, ki);
    kiir("result.txt");
  }
  else if(argc == 3)
  {
//    Tiles startTiles, ref;
//    beolvas(argv[1], startTiles);
//    globalBest = mtxSize;
//    for(int i=0;i<12;++i)
//    {
        Tiles startTiles, ref;
        beolvas(argv[1], startTiles);
        beolvas(argv[2], ref);
        for(int i=0;i<3;i++) {
            for(int j=0;j<3;j++)
                cout<<count(startTiles,ref,i,j)<<" ";
            cout<<endl;
        }
        reOrderWrapper(startTiles, ref);
        std::cout<<"Best: "<<bestSwaps.size()/2<<std::endl;
//        if(i==0) ref = buildRowStyleTiles(startTiles,0,1,2);
//        if(i==1) ref = buildRowStyleTiles(startTiles,0,2,1);
//        if(i==2) ref = buildRowStyleTiles(startTiles,1,0,2);
//        if(i==3) ref = buildRowStyleTiles(startTiles,1,2,0);
//        if(i==4) ref = buildRowStyleTiles(startTiles,2,0,1);
//        if(i==5) ref = buildRowStyleTiles(startTiles,2,1,0);
//        if(i==6) ref = buildColumnStyleTiles(startTiles,0,1,2);
//        if(i==7) ref = buildColumnStyleTiles(startTiles,0,2,1);
//        if(i==8) ref = buildColumnStyleTiles(startTiles,1,0,2);
//        if(i==9) ref = buildColumnStyleTiles(startTiles,1,2,0);
//        if(i==10) ref = buildColumnStyleTiles(startTiles,2,0,1);
//        if(i==11) ref = buildColumnStyleTiles(startTiles,2,1,0);
//        Tiles bestRef;
//        improveCount=0;
//        improve(startTiles, ref, bestRef);
//        reOrderWrapper(startTiles, bestRef);
//        std::cout<<"Best: "<<bestSwaps.size()/2<<std::endl;
//    }
    //std::cout<<"Result\n";
    //showTiles(result);
    kiir("resultrev.txt");
    cout<<connected(startTiles)<<endl;
  }
  else
    std::cout<<"Required 1 or 2 parameters\n";
}
